package com.LeeCode;

import java.util.Arrays;

/**
 * 正方形中的最多点数
 */

public class Code3143 {
    public static void main(String[] args) {

    }

    private int ans;

    public int maxPointsInsideSquare(int[][] points, String S) {
        char[] s = S.toCharArray();
        int left = -1;
        int right = 1_000_000_001;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid, points, s)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return ans;
    }

    private boolean check(int size, int[][] points, char[] s) {
        int vis = 0;
        for (int i = 0; i < points.length; i++) {
            // 判断点是否在正方形中
            if (Math.abs(points[i][0]) <= size && Math.abs(points[i][1]) <= size) {
                int c = s[i] - 'a';
                if ((vis >> c & 1) > 0) { // c 在集合中
                    return false;
                }
                vis |= 1 << c; // 把 c 加入集合
            }
        }
        ans = Integer.bitCount(vis);
        return true;
    }

    public int maxPointsInsideSquare1(int[][] points, String s) {
        int[] minD = new int[26];
        Arrays.fill(minD, Integer.MAX_VALUE);
        int min2 = Integer.MAX_VALUE;
        char[] chars = s.toCharArray();
        for (int i = 0; i < points.length; i++) {
            int dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
            int index = chars[i] - 'a';
            if (dist < minD[index]) {
                min2 = Math.min(min2, minD[index]);
                minD[index] = dist;
            } else {
                min2 = Math.min(min2, dist);
            }
        }
        int ans = 0;
        for (int min : minD) {
            if (min < min2)
                ans++;
        }
        return ans;
    }
}
